/**
 * 给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * 单向链表实现归并排序（递归实现）
 * https://leetcode.cn/problems/7WHec2/
 */
class SortListGuiBin {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode slow=head;
        ListNode fast=head;
        ListNode pre=head;
        while(fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;
        ListNode l1=sortList(head);
        ListNode l2=sortList(slow);
        return meger(l1,l2);
    }
    public ListNode meger(ListNode l1,ListNode l2){
        ListNode newHead=new ListNode();
        ListNode cur=newHead;
        ListNode headA=l1;
        ListNode headB=l2;
        while(headA!=null&&headB!=null){
            if(headA.val<headB.val){
                cur.next=headA;
                cur=headA;
                headA=headA.next;
                
            }else{
                cur.next=headB;
                cur=headB;
                headB=headB.next;
                
            }
        }
        if(headA!=null){
            cur.next=headA;
        }
        else if(headB!=null){
            cur.next=headB;
        }
        return newHead.next;
    }
}